package problem86_Partition_List;

import problem82_Remove_Duplicates_from_Sorted_List2.ListNode;

public class MySolution {
	public ListNode partition(ListNode head, int x) {  
        if (head==null || head.next==null) {  
            return head;  
        }  
        ListNode s = new ListNode(0);//small partition  
        ListNode p = s;  
        ListNode l = new ListNode(0);//large partition  
        ListNode q = l;  
        while(head!=null){  
            if (head.val<x) {  
                p.next = head;  
                p = p.next;  
            }else {  
                q.next = head;  
                q = q.next;  
            }  
            head = head.next;  
        }  
        q.next = null;  
        p.next = l.next;  
        return s.next;  
    }  
	
	public static void main(String[] args){
		ListNode node1=new ListNode(1);
		ListNode node2=new ListNode(4);
		ListNode node3=new ListNode(3);
		ListNode node4=new ListNode(2);
		ListNode node5=new ListNode(5);
		ListNode node6=new ListNode(2);
		node1.next=node2;
		node2.next=node3;
		node3.next=node4;
		node4.next=node5;
		node5.next=node6;
		ListNode head=new MySolution().partition(node1, 3);
		while(head!=null){
			System.out.print(head.val+"->");
			head=head.next;
		}
	}
}
